class Solution {
public:
    string minWindow(string s, string t) {
        int left = 0, right = 0;
        int len = 1e9;
        int kinds = 0;
        int count = 0;
        unordered_map<int, int> m2;
        unordered_map<int, int> m1;
        string s3;
        int begin = -1;
        for (int i = 0; i < t.length(); i++)
        {
            if (m2[t[i]] == 0) kinds++;
            m2[t[i]]++;
        }
        while (right < s.length())
        {
            m1[s[right]]++;
            if (m2[s[right]] == m1[s[right]]) count++;
            while (count == kinds)
            {
                if (len > right - left + 1)
                {
                    len = right - left + 1;
                    begin = left;
                }
                if (m1[s[left]] == m2[s[left]] && m2[s[left]] != 0)
                {
                    count--;
                }
                m1[s[left]]--;
                left++;
            }
            right++;
        }
        if (begin == -1) {
            return "";
        }
        else return s.substr(begin, len);
    }
};